\documentclass[11pt, a4paper]{article}


% Configuración de márgenes de las páginas
	%\usepackage[left=3cm,right=3cm,top=2cm, bottom=2cm]{geometry}
	\usepackage{a4wide}

% Paquete de acentos para Linux
	\usepackage[utf8]{inputenc}

% Paquete de acentos para windows
%	\usepackage[latin1]{inputenc}

% Paquete para reconocer la separación en sílabas en español
	\usepackage[spanish]{babel}

% Paquetes especiales para el TP
	\usepackage{./otros/caratula}


% Paquete para incluir hypervinculos
	\usepackage{color}
	\usepackage{url}
	\definecolor{lnk}{rgb}{0,0,0.4}
	\usepackage[colorlinks=true,linkcolor=lnk,citecolor=blue,urlcolor=blue]{hyperref}

% Paquete para armar índices
	\usepackage{makeidx}
	\makeindex

% Más espacio entre líneas
	\parskip=1.5pt


\begin{document}

% Carátula
	\titulo{Trabajo Práctico - Postscript Parser}
	\fecha{7 de Julio de 2011}
	\materia{Teoría de Lenguajes}
	\integrante{Carrillo, Facundo}{693/07}{facu.zeta@gmail.com}
	\integrante{Bianchi, Mariano}{92/08}{marianobianchi08@gmail.com}
	\integrante{Brusco, Pablo}{527/08}{pablo.brusco@gmail.com}
	\maketitle

% Índice
\newpage \printindex \tableofcontents

\newpage
\section{Planteo de la gramática}

\label{gramatica}

\paragraph{}
En primer lugar, se debió pensar una gramática que generara el lenguaje F presentado en el enunciado del presente trabajo práctico. Luego de plantear esto, debíamos pasar dicha gramática a la herramienta generadora de parsers elegida. En nuestro caso, las herramientas elegidas fueron YACC y FLEX, por lo que al pensar la gramática, debimos corroborar que la misma fuese del tipo LALR, ya que éstas son el tipo de gramática soportado por YACC.
\vspace{10pt}
Luego de varios intentos y pruebas, se llegó a la siguiente gramática:\\
\vspace{10pt}
$graficos \rightarrow\ \lambda\ |\ graficos\ grafico$ \\
\vspace{10pt}
$grafico \rightarrow\ atomico\ |\ definicion\ |\ repeticion\ |\ rotacion\ |\ mover\ |\ escalar$ \\
\vspace{10pt}
$repeticion \rightarrow\ repeat\ int\ float\ float\ grafico$ \\
\vspace{10pt}
$rotacion \rightarrow\ rotate\ float\ grafico$ \\
\vspace{10pt}
$mover \rightarrow\ move\ float\ float\ grafico$ \\
\vspace{10pt}
$escalar \rightarrow\ scale\ float\ float\ grafico$ \\
\vspace{10pt}
$atomico \rightarrow\ box\ float\ float\ |\ circle\ float\ |\ (\ graficos\ )$


\newpage
\section{Flex}
Luego de generar esta gramática, debíamos pasar a trabajar con las herramientas recomendadas comenzando, en nuestro caso, por FLEX. Esta herramienta, nos permite reconocer cadenas de caracteres y tokenizarlas. Esto es de gran utilidad, ya que YACC no tiene este potencial. La idea entonces fue reconocer las cadenas que debían pertenecer al lenguaje (ej $box\ 1\ -.4$). Para ello, según la sintaxis de FLEX, se definen las reglas que se utilizaran para reconocer las distintas cadenas, y las acciones que se llevaran a cabo para cada posible matching.

En este caso, las reglas que definen el lenguaje F constan de tres casos distintos de acciones:
\begin{itemize}
	\item Aquel en el que sólo interesa devolver el TOKEN correspondiente a la cadena que matcheó la regla.
	\item Aquel en el que, además de devolver el TOKEN correspondiente a la cadena que matcheó la regla, guarda en la pila del parser el valor numérico descripto por dicha cadena.
	\item Aquel en el que, además de devolver el TOKEN correspondiente a la cadena que matcheó la regla, guarda en la pila del parser el valor alfanumérico descripto por dicha cadena.
\end{itemize}

Los TOKENS aquí mencionados hacen referencia a código generado por YACC. Estos TOKENS junto con los parámetros de manejo de pila del parser, son ejemplos de interacciones entre ambas herramientas.

\newpage
\section{YACC}
Más tarde, una vez testeado el funcionamiento del código FLEX, se pasó a trabajar con YACC. Lo primero que se hizo fue transcribir la gramática nombrada en la sección [\ref{gramatica}]. Esto se realizó de manera sencilla, ya que sólo había que cambiar los no terminales por TOKENS definidos previamente en YACC.

Una vez reescrita la gramática al ``estilo YACC'', pasamos a definir en qué momentos y cómo podía ir parseandose la entrada a lenguaje PostScript. Basicamente, cada vez que se matcheaba alguna regla de la gramática, se iba escribiendo en la salida (ya sea archivo o por pantalla) la traducción correspondiente a la cadena (cadena tokenizada) recibida como input. El orden de esta escritura depende de cada regla, según si debe escribir algo que englobe a una subcadena o si primero se escribe todo lo correspondiente a la cadena y luego se continúa con el resto del input (o viceversa).

El mayor problema que presentaba este lenguaje es que se permitía al usuario definir sus propias funciones para después poder reutilizarlas. Esto nos obligaba a aceptar cualquier cadena alfanumérica, ya que si en un momento se lee un ``define nombreDeFuncion grafico'', luego en el texto es válido que aparezca la cadena ``nombreDeFuncion''. Para solucionar esto, se decidió definir un conjunto de nombres, el cuál comienza con las entradas correspondientes a las funciones ya existentes en PostScript. Por ejemplo, este conjunto va a tener siempre entre sus entradas a ``repeat'', porque no sería deseable redefinir el significado de dicha función. Luego, cada vez que se encontrase un matching concordante con un ``define'' se verificaba si este ya habia sido definido anteriormente. Si esto sucedía, se devolvía un error informando del problema. Sino, se agregaba al conjunto de definiciones y se continuaba el flujo normal del programa. Algo similar se debió hacer para el caso que se encontrara un matching con una cadena cualquiera que no coincidiera con ninguna del lenguaje F. En este caso, se verificaba si dicha cadena estaba definida en el conjunto antes mencionado. Si lo estaba, no había ningún problema y se continuaba normalmente. En caso que no existiera una definición para esa cadena, se finalizaba la ejecución informando el error producido.

\section{Ejemplos}

\subsection{Ejemplos válidos}
A mdo de test se decidio implentar diversos test por función. \\
Luego de pasar dichos test se abordo a combinar funciones y generar gráficos mas complejos.
\medskip
Para probar los ejemplos que habia en el enunciado se decidio enmarcarlos en el siguente contexto para lograr observarlos bien
	
\begin{verbatim}
move 0 350 box 1000 0.1
move 300 0 box 0.1 1000

move 300 350 (
   scale 20 20(

    CODIGO

  )
)
\end{verbatim}

Los casos provistos en el enunciado son tranformados de la siguente manera:

\begin{itemize}
 \item Ejemplo 1
    \begin{verbatim}
    circle .5
    box 1 1
    \end{verbatim}

    y se tranforma en


    \begin{verbatim}
    gsave 0.500000 0.500000 scale circ grestore
    gsave 1.000000 1.000000 scale box grestore 
    \end{verbatim}
\item Ejemplo 2	

    \begin{verbatim}
    move -2 -2 repeat 4 0 1
		repeat 2 .5 .5
		  repeat 4 1 0
		    box .5 .5
    \end{verbatim}

    y se tranforma en


    \begin{verbatim}
    gsave -2.000000 -2.000000 translate gsave 4 {
      gsave 2 { 
	gsave 4 {
	    gsave 0.500000 0.500000 scale box grestore 1.000000 0.000000 translate
	} repeat grestore 0.500000 0.500000 translate }
    repeat grestore 0.000000 1.000000 translate }
    repeat grestore  grestore 
    \end{verbatim}

\end{itemize}



\subsection{Ejemplos inválidos}

\begin{itemize}
 \item Ejemplo 1
    \begin{verbatim}
    define define (rotate 45 box 10 10)
    \end{verbatim}
No se permite redefinir una palabra reservada.

\item Ejemplo 2
    \begin{verbatim}
      scale 2 circle 3
    \end{verbatim}
Falta un parámetro en el scale

\item Ejemplo 3
    \begin{verbatim}
      move 3 4 rombo
    \end{verbatim}
Rombo no está definido.

\item Ejemplo 4
    \begin{verbatim}
      move 3 4 define rombo (rotate 45 box 10 10)
    \end{verbatim}
move espera un gráfico como tercer parámetro, pero define no es un gráfico.

\end{itemize}


%\medskip

\section{C\'odigo}
\subsection{Lex}
\begin{verbatim}
%{
	#include <stdio.h>
	#include "pruebaYacc.yy.h"
	
%}

%%

[Cc][Ii][Rr][Cc][Ll][Ee]	return TOKCIRCLE;
[Bb][Oo][Xx]			return TOKBOX;
[-]?[0-9]*(["."])?[0-9]+		yylval.real=atof(yytext); return REAL;
[Mm][Oo][Vv][Ee]		return TOKMOVE;
[Rr][Oo][Tt][Aa][Tt][Ee]	return TOKROTATE;
[Ss][Cc][Aa][Ll][Ee]		return TOKSCALE;
[Rr][Ee][Pp][Ee][Aa][Tt]	return TOKREPEAT;
[Dd][Ee][Ff][Ii][Nn][Ee]	return TOKDEFINE;
[a-zA-Z][a-zA-Z0-9]*		yylval.name=yytext; return NAME;
\n                   		/* ignore end of line */;
[ \t]+             		/* ignore whitespace */;
\(				return TOKABRIRPARENTESIS;
\)				return TOKCERRARPARENTESIS;

%%

\end{verbatim}

\subsection{Yacc}
\footnotesize
\begin{verbatim}
%{
#include <stdio.h>
#include <iostream>
#include <set>
#include <ctype.h>

using namespace std;

set<string> *conjunto_def;

void tolowerStr(char * str){
	int i=0;
	
	while(str[i]!=0){
		str[i] = tolower(str[i]);
		i++;
	}
	
}

extern "C"
{
		
        int yylex(void); 
        extern FILE* yyin;
        int yywrap()
        {
                return 1;
        }
        
}


void yyerror(const char *str)
{
        fprintf(stderr,"error: %s\n",str);
}

FILE * salida;

%}


%token TOKDEFINE TOKMOVE TOKSCALE TOKROTATE TOKREPEAT TOKBOX TOKCIRCLE 
TOKABRIRPARENTESIS TOKCERRARPARENTESIS


%union 
{
        float real;
        char* name;
}

//%token <real> REAL
%left <real> REAL
%token <name> NAME



%%

graficos:
	|
	graficos grafico
	|
	graficos definicion
	;	
grafico:
	atomico
	|
	repeticion
	|
	rotacion
	|
	mover
	|
	escalar
	;
definicion:
	TOKDEFINE NAME {
		
		char *name= $2;
		tolowerStr(name);
		
		//Chequeamos si ya estaba defindo
		if (conjunto_def->find(name) != conjunto_def->end()){
					
					
					char error_msg[50];
					sprintf(error_msg,"Intenta definir %s cuando ya estaba definida antes.", name);
					yyerror(error_msg);
					
				//por si lo de arriba no corta ejecucion
				while(1);
		}
		//Lo guardo en el conjunto
				conjunto_def->insert(name);
		
				printf("/%s {",name);
		
		
		} grafico {{printf("} def ");}}
	;
	
repeticion:
	TOKREPEAT REAL REAL REAL {printf("gsave %d { ",(int) $2);} grafico 
{printf("%f %f translate } repeat grestore ",$3,$4);}
	;

rotacion:
	TOKROTATE REAL {printf("gsave %f rotate ",$2);} grafico {printf(" grestore ");}
	;
	
mover:
	TOKMOVE REAL REAL {printf("gsave %f %f translate ",$2,$3);} grafico {printf(" grestore ");}
	;
	
escalar:
	TOKSCALE REAL REAL {printf("gsave %f %f scale ",$2,$3);} grafico {printf(" grestore ");} 
	;
		
atomico:
	TOKBOX REAL REAL {printf("gsave %f %f scale box grestore ",$2,$3);}
	|
	TOKCIRCLE REAL {printf("gsave %f %f scale circ grestore ",$2,$2);}
	|
	TOKABRIRPARENTESIS graficos TOKCERRARPARENTESIS
	|
	NAME {
		
		char *name= $1;
		tolowerStr(name);
		
		if (conjunto_def->find(name) != conjunto_def->end()){
			printf("gsave %s grestore ",name);
		}else{
			char error_msg[50];
			sprintf(error_msg,"Usa %s sin haberlo definido antes.", name);
			yyerror(error_msg);
					
			
		}
		
	}
	;
%%

main(int argc,char *argv[])
{	
	//Creamos el conjunto de definiciones
    set<string> conjunto;
    conjunto_def = &conjunto;
    
    
	if (argc>1){
		printf("Modo archivo \n");
	//printf("cantargs:%d \n filename:%s\n",argc, argv[1]);
		
		FILE * entrada=fopen(argv[1],"r");
        yyin=entrada;
        
        string nombre = ((string) argv[1])+".eps";
        freopen (nombre.c_str(),"w",stdout);
      
        
    } else{
		  printf("Modo consola \n");
		  yyin= NULL;
		  
  }
    
    
        printf( "%%Prologo generico.\n \
		5 dict begin\n \
		/box {\n \
		\t0 0 moveto 0 1 lineto 1 1 lineto 1 0 lineto closepath fill\n\
		} def\n\n\
		/circ {\n \
		\t0 0 1 0 360 arc closepath fill\n\
		} def\n\
		%%Fin prologo. Comienzo grafico.\n\n");

        yyparse();
        
        printf("\nend\nshowpage");
} 

\end{verbatim}
\normalsize



\section{Modo de uso}
En la carpeta SRC, se encuentra el c\'odigo, para compilarlo se provee de un makefile. 
Una vez compilado se puede ejecutar pasandole 1 o ning\'un parámetro
el cual ind\'ica el nombre de archivo de entrada.La traducción es devuelta en un archivo con el mismo nombre que
el de la entrada con extensi\'on eps o por consola en caso de no proveerlo. 

\section{Gr\'aficos}
Para imprimir los gr\'aficos se utilizo la siguiente macro, que translada el centro de coordenadas al centro de la p\'agina:


\begin{verbatim}
move 0 350 box 1000 0.1
move 300 0 box 0.1 1000

move 300 350 (
  scale 20 20(

----------CODIGO EN F DEL GRAFICO----------

	)

)
\end{verbatim}

generando los siguentes resultados para los ejemplos del enunciado.

\begin{figure}
\centering
\includegraphics[scale=0.4]{1.pdf}
\caption[]{}
\label{f.comp}
\end{figure}

\begin{figure}
\centering
\includegraphics[scale=0.4]{2.pdf}
\caption[]{}
\label{f.comp}
\end{figure}
\begin{figure}
\centering
\includegraphics[scale=0.4]{3.pdf}
\caption[]{}
\label{f.comp}
\end{figure}
\begin{figure}
\centering
\includegraphics[scale=0.4]{4.pdf}
\caption[]{}
\label{f.comp}
\end{figure}
\begin{figure}
\centering
\includegraphics[scale=0.4]{5.pdf}
\caption[]{}
\label{f.comp}
\end{figure}
\begin{figure}
\centering
\includegraphics[scale=0.4]{6.pdf}
\caption[]{}
\label{f.comp}
\end{figure}
\begin{figure}
\centering
\includegraphics[scale=0.4]{7.pdf}
\caption[]{}
\label{f.comp}
\end{figure}
\begin{figure}
\centering
\includegraphics[scale=0.4]{8.pdf}
\caption[]{}
\label{f.comp}
\end{figure}



%A modo de ejemplo, aquí se muestran dos códigos distintos en F y su respectiva imagen resultante en PostScript.


\end{document}
